package Classic150;

import java.util.Arrays;

public class 用最少数量的箭引爆气球 {
    /*
        排序，贪心，注意排序规则使用Integer.compare()防止计算超出范围
     */
    public int findMinArrowShots(int[][] points) {
        int len = points.length;
        if (len == 1) return 1;
        Arrays.sort(points, (a, b) -> a[0] == b[0] ? Integer.compare(a[1], b[1]) : Integer.compare(a[0], b[0]));
        int min = 1;
        int boundary = points[0][1];
        for (int i = 1; i < len; i++) {
            if (points[i][0] > boundary) {
                min++;
                boundary = points[i][1];
            } else boundary = Math.min(boundary, points[i][1]);
        }
        return min;
    }
}
